package 字符串.正则;

import 抽象数据类型.Digraph;
import 图.有向图.有向图的可达性;
import 抽象数据类型.Bag;

import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-09-12
 */
public class 正则表达式模式匹配 {
    public static void main(String[] args) {
        String regexp = "(.*" + "abc" + ".*)";
        String[] txt = new String[]{"abc", "cac", "aabc"};
        NFA nfa = new NFA(regexp);
        for (String s : txt) {
            System.out.println(nfa.recognizes(s));
        }



    }
    public static class NFA {
        private char[] re; //匹配转换
        private Digraph G;//epsilon转换
        private int M;//状态数量

        public NFA(String regexp) {
            Stack<Integer> ops = new Stack<Integer>();
            re = regexp.toCharArray();
            M = re.length;
            G = new Digraph(M + 1);
            for (int i = 0; i < M; i++) {
                int lp = i;
                if (re[i] == '(' || re[i] == '|') {
                    ops.push(i);
                } else if (re[i] == ')') {
                    int or = ops.pop();
                    if (re[or] == '|') {
                        lp = ops.pop();
                        G.addEdge(lp, or + 1);
                        G.addEdge(or, i);
                    } else {
                        lp = or;
                    }
                }
                if (i < M - 1 && re[i + 1] == '*') { //查看下一个字符
                    G.addEdge(lp, i + 1);
                    G.addEdge(i + 1, lp);
                }
                if (re[i] == '(' || re[i] == '*' || re[i] == ')') {
                    G.addEdge(i, i + 1);
                }
            }
        }

        public boolean recognizes(String txt) {
            Bag<Integer> pc = new Bag<>();
            有向图的可达性.DirectedDFS dfs = new 有向图的可达性.DirectedDFS(G, 0);
            for (int v = 0; v < G.V(); v++) {
                if (dfs.marked(v)) {
                    pc.add(v);
                }
            }
            for (int i = 0; i < txt.length(); i++) {
                Bag<Integer> match = new Bag<>();
                //计算txt[i+1] 可能到达的所有NFA状态
                for (Integer v : pc) {
                    if (v < M) {
                        if (re[v] == txt.charAt(i) || re[v] == '.') {
                            match.add(v + 1);
                        }
                    }
                }
                pc = new Bag<>();
                dfs = new 有向图的可达性.DirectedDFS(G, match);
                for (int v = 0; v < G.V(); v++) {
                    if (dfs.marked(v)) {
                        pc.add(v);
                    }
                }
            }
            for (Integer v : pc) {
                if (v == M) {
                    return true;
                }
            }
            return false;
        }
    }
}
